#define  _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 不同路径
class Solution
{
public:
	int uniquePaths(int m, int n)
	{
		// 1、建表
		// 2、初始化
		// 3、填表
		// 4、返回值
		vector<vector<int>> dp(m + 1, vector<int>(n + 1));
		dp[0][1] = 1;
		for (size_t i = 1; i <= m; ++i)
			for (size_t j = 1; j <= n; ++j)
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		return dp[m][n];
	}
};

// 解码方法
////class Solution
//{
//public:
//	int numDecodings(string s)
//	{
//		// 1、建表
//		size_t n = s.size();
//		vector<int> dp(n + 1);
//
//		// 2、初始化
////		dp[0] = 1;
////		dp[1] = s[0] != '0';
////
////		// 3、填表
////		for (size_t i = 2; i <= n; ++i)
////		{
////			if (s[i - 1] != '0') dp[i] += dp[i - 1];
////			if (atoi(s.substr(i - 2, 2).c_str()) >= 10 && atoi(s.substr(i - 2, 2).c_str()) <= 26) dp[i] += dp[i - 2];
////		}
////
////		// 4、返回值
////		return dp[n];
////	}
////};

//class Solution
//{
//public:
//	int numDecodings(string s)
//	{
//		if (s[0] == '0')
//			return 0;
//		if (s.size() == 1)
//			return 1;
//
//		size_t n = s.size();
//		vector<int> dp(n+1);
//		dp[0] = 1, dp[1] = 1;
//		if (dp[2] != '0') dp[2] += dp[1];
//		if (dp[1] != '0' && atoi(s.substr(0, 2).c_str()) < 27) dp[2] += dp[0];
//
//		for (size_t i = 3; i <= n; ++i)
//		{
//			if (dp[i] != '0') dp[i] += dp[i-1];
//			if (dp[i-1] != '0' && atoi(s.substr(i-2, 2).c_str()) < 27) dp[i] += dp[i-2];
//		}
//
//		return dp[n];
//	}
//};

//class Solution
//{
//public:
//	int numDecodings(string s)
//	{
//		if (s[0] == '0')
//			return 0;
//
//		size_t n = s.size();
//		vector<int> dp(n);
//		dp[0] = 1;
//		if (n > 1)
//		{
//			if (s[1] == '0')
//				dp[1] = 1;
//			else
//				dp[1] = 2;
//		}
//
//		for(size_t i = 2; i < n; ++i)
//		{
//			if (dp[i] != '0')
//				dp[i] += dp[i - 1];
//			if (dp[i - 1] != '0')
//				dp[i] += dp[i - 2];
//		}
//		return dp[n - 1];
//	}
//};